package java学习.算法.二叉树;

import java.util.*;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/1 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */

//     class TreeNode {
//        int val = 0;
//        TreeNode left = null;
//        TreeNode right = null;
//        public TreeNode(int val) {
//            this.val = val;
//        }
//    }

    public class TreeNodeByK {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param proot TreeNode类
         * @param k int整型
         * @return int整型
         */
        public int KthNode (TreeNode proot, int k) {
            // write code here
            if (proot==null){
                return -1;
            }
            return getvalList(proot,k);

        }
        // 先序遍历二叉树
        public static int getvalList(TreeNode proot,int k){
            List<Integer> list = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<>();
            stack.push(proot);
            while(!stack.empty()){
                TreeNode n = stack.pop();
                list.add(n.val);
                if(n.left!=null){
                    stack.push(n.left);
                }
                if(n.right!=null){
                    stack.push(n.right);
                }
            }
            Collections.sort(list);
            return (k<=0 || list.size()<k )? -1: list.get(k-1);

//              Object[] array = list.toArray();
//            Arrays.sort( array);
//             int n = array.length;
//            return (k<=0 || n<k )? -1: (int) array[k-1];

        }
    public static int getvalList1(TreeNode proot,int k){
        List<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(proot);
        while(!queue.isEmpty()){
            TreeNode n = queue.poll();
            list.add(n.val);
            if(n.left!=null){
                queue.offer(n.left);
            }
            if(n.right!=null){
                queue.offer(n.right);
            }
        }
        Collections.sort(list);
        return (k<=0 || list.size()<k )? -1: list.get(k-1);

//              Object[] array = list.toArray();
//            Arrays.sort( array);
//             int n = array.length;
//            return (k<=0 || n<k )? -1: (int) array[k-1];

    }
    }
